package com.mypaper.schedule;

import com.mypaper.dag.DAG;
import com.mypaper.elem.LinkedListNode;
import com.mypaper.elem.PairElement;
import com.mypaper.elem.ScheduleElement;
import com.mypaper.elem.ScheduleNode;
import com.mypaper.elem.TaskNode;
import com.mypaper.list.OrderLinkedList;
import com.mypaper.list.ScheduleResults;



public class CPOPSchedule {
	public ScheduleResults scheduleResults;
	public float[] AST;
	public float[] AFT;
	public int[] assiProc2Task;
	OrderLinkedList[] idleTimeList;
	
	public CPOPSchedule(DAG dag){
		scheduleResults=new ScheduleResults();
		assiProc2Task=new int[dag.vertexNum];
		AST=new float[dag.vertexNum];//每个任务在遍历所有处理器后计算出的实际开始执行时间
		AFT=new float[dag.vertexNum];//每个任务在遍历所有处理器后计算出的实际结束执行时间	
		idleTimeList=new OrderLinkedList[dag.procNum];//每个处理器一个空闲时间块列
		for(int i=0; i<dag.procNum; i++){
			idleTimeList[i]=new OrderLinkedList();
			idleTimeList[i].insertNode(new PairElement(0,Float.MAX_VALUE));
		}
	}
	
	public void CPOP_Algorithm(DAG dag){
		int i,j;
		int currTaskIndex=-1;
		
		float[][] EST=new float[dag.vertexNum][dag.procNum];//每个任务在遍历每个处理器时计算出的最早开始执行时间
		float[][] EFT=new float[dag.vertexNum][dag.procNum];//每个任务在遍历每个处理器时计算出的最早结束执行时间
		float[][] DAT=new float[dag.vertexNum][dag.procNum];
		float[][] readyTime=new float[dag.vertexNum][dag.procNum];
		
		for(i=0; i<dag.vertexNum; i++){
			AST[i]=Float.MAX_VALUE;
			AFT[i]=Float.MAX_VALUE;
			assiProc2Task[i]=-1;
			for(j=0; j<dag.procNum; j++){
				EST[i][j]=Float.MAX_VALUE;
				EFT[i][j]=Float.MAX_VALUE;
				DAT[i][j]=0;
				readyTime[i][j]=0;
			}
		}
			
		float AFT_back=Float.MAX_VALUE;
		float AST_back=Float.MAX_VALUE;
		
		PairElement searchItem=new PairElement(), beFoundItem=new PairElement();
		PairElement searchItemBack=new PairElement(), beFoundItemBack=new PairElement();
	
		TaskNode currentTask=dag.priorCPOP.first;
		while(currentTask!=null){
			currTaskIndex=currentTask.info.index;
			
			if(Math.abs(dag.btLevel[currTaskIndex]-dag.CPLength)>0.0001){//找CP上的任务
				for(int k=0; k<dag.procNum; k++){
					for(int l=0; l<dag.vertexNum; l++){
						if(dag.edgeWeight[l][currTaskIndex]!=0){
							if(assiProc2Task[l]==k)//对于每个父节点，求到达处理器的时间
								DAT[l][k]=AFT[l];
							else{
								DAT[l][k]=AFT[l]+dag.edgeWeight[l][currTaskIndex];
							}
							if(readyTime[currTaskIndex][k]<DAT[l][k]){//找MIIP父节点及其到达时间
								readyTime[currTaskIndex][k]=DAT[l][k];
							}
						}
					}
				
					
					
					boolean found=false;
					
					searchItem.setNum(readyTime[currTaskIndex][k],readyTime[currTaskIndex][k]+dag.vertexWeight[currTaskIndex][k]);
					//要为searchItem找合适的空闲时间
					beFoundItem=(PairElement)idleTimeList[k].search(searchItem);//beFoundItem为找到的空闲时间段
					//System.out.print(beFoundItem);
					if(beFoundItem!=null)
						found=true;
					
					if(found==true){
						EST[currTaskIndex][k]=Math.max(readyTime[currTaskIndex][k], beFoundItem.start);
						EFT[currTaskIndex][k]=EST[currTaskIndex][k]+dag.vertexWeight[currTaskIndex][k];
						
					}
					
					if(AFT_back>EFT[currTaskIndex][k]){
						searchItemBack=(PairElement)searchItem.getCopy();
						beFoundItemBack=(PairElement)beFoundItem.getCopy();
						AFT_back=EFT[currTaskIndex][k];
						assiProc2Task[currTaskIndex]=k;
					}
				}
				
				AFT[currTaskIndex]=AFT_back;
				AST[currTaskIndex]=AFT[currTaskIndex]-dag.vertexWeight[currTaskIndex][assiProc2Task[currTaskIndex]];
				AFT_back=Float.MAX_VALUE;
				
				idleTimeList[assiProc2Task[currTaskIndex]].deleteNode(beFoundItemBack);
				if(searchItemBack.start>beFoundItemBack.start){
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(beFoundItemBack.start,EST[currTaskIndex][assiProc2Task[currTaskIndex]]));
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(EFT[currTaskIndex][assiProc2Task[currTaskIndex]],beFoundItemBack.end));
				}else{
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(EFT[currTaskIndex][assiProc2Task[currTaskIndex]],beFoundItemBack.end));
				}

				ScheduleElement perTask=new ScheduleElement();
				perTask.setNum(currTaskIndex,assiProc2Task[currTaskIndex],AST[currTaskIndex],AFT[currTaskIndex]);
				scheduleResults.insertNode(perTask);
				currentTask=currentTask.next;
				
			}else{
				
				for(int l=0; l<dag.vertexNum; l++){
					if(dag.edgeWeight[l][currTaskIndex]!=0){
						if(assiProc2Task[l]==dag.selectedProcCPOP)//对于每个父节点，求到达处理器的时间
							DAT[l][dag.selectedProcCPOP]=AFT[l];
						else{
							DAT[l][dag.selectedProcCPOP]=AFT[l]+dag.edgeWeight[l][currTaskIndex];
						}
						if(readyTime[currTaskIndex][dag.selectedProcCPOP]<DAT[l][dag.selectedProcCPOP]){//找MIIP父节点及其到达时间
							readyTime[currTaskIndex][dag.selectedProcCPOP]=DAT[l][dag.selectedProcCPOP];
						}
					}
				}
				float RT=readyTime[currTaskIndex][dag.selectedProcCPOP];
				LinkedListNode currentIdle=idleTimeList[dag.selectedProcCPOP].first;
				boolean found=false;
				while(currentIdle!=null&&!found){
					searchItem.setNum(RT,RT+dag.vertexWeight[currTaskIndex][dag.selectedProcCPOP]);
					//要为searchItem找合适的空闲时间
					beFoundItem=(PairElement)idleTimeList[dag.selectedProcCPOP].search(searchItem);//beFoundItem为找到的空闲时间段
					//System.out.print(beFoundItem);
					if(beFoundItem!=null)
						found=true;
					currentIdle=currentIdle.next;
				}
				if(found==true){
					AST_back=Math.max(RT, beFoundItem.start);
					AFT_back=AST_back+dag.vertexWeight[currTaskIndex][dag.selectedProcCPOP];
					assiProc2Task[currTaskIndex]=dag.selectedProcCPOP;
					searchItemBack=(PairElement)searchItem.getCopy();
					beFoundItemBack=(PairElement)beFoundItem.getCopy();
				}
				
				AFT[currTaskIndex]=AFT_back;
				AST[currTaskIndex]=AST_back;
				AFT_back=Float.MAX_VALUE;
				
				idleTimeList[assiProc2Task[currTaskIndex]].deleteNode(beFoundItemBack);
				if(searchItemBack.start>beFoundItemBack.start){
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(beFoundItemBack.start,AST[currTaskIndex]));
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(AFT[currTaskIndex],beFoundItemBack.end));
				}else{
					idleTimeList[assiProc2Task[currTaskIndex]].insertNode(new PairElement(AFT[currTaskIndex],beFoundItemBack.end));
				}

				ScheduleElement perTask=new ScheduleElement();
				perTask.setNum(currTaskIndex,assiProc2Task[currTaskIndex],AST[currTaskIndex],AFT[currTaskIndex]);
				scheduleResults.insertNode(perTask);
				currentTask=currentTask.next;
			}
		}
	}
	
	public float energyCal(int procNum){
		float enerSum=0;
        float timeSum=0;	
        float totalTime=0;
        float power=(float)0.925, idlePower=(float)0.260;
        boolean[] flag=new boolean[procNum];
        float[] procTermTime=new float[procNum];
        ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			ScheduleElement perTask=currentTask.info;
			if(flag[perTask.processorID]!=true)
				flag[perTask.processorID]=true;
			if(perTask.endTime>procTermTime[perTask.processorID])
				procTermTime[perTask.processorID]=perTask.endTime;
			timeSum+=(perTask.endTime-perTask.startTime);
			currentTask=currentTask.next;
		}
		
		for(int i=0; i<procNum; i++){
			System.out.println("End time of processor "+i+" is "+procTermTime[i]);
			totalTime+=procTermTime[i];
		}
		
		enerSum=timeSum*power+(totalTime-timeSum)*idlePower;
		return enerSum;
	}
	
	
	public float makespan(){
		float curr=0;
		ScheduleNode currentTask=scheduleResults.first;
		while(currentTask!=null){
			
			if(curr<currentTask.info.endTime)
				curr=currentTask.info.endTime;
			currentTask=currentTask.next;
		}
		return curr;
	}
}

